/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-26
 * Time:14:34
 * Text：面试题 08.01. 三步问题
 */
public class Text3 {
    int num=0;
    int count=0;
    public void ways(int n) {
        if(num==n){
            count++;
        }
        if(n>=num){
            return;
        }
        for(int i=1;i<4;i++){
            ways(n+i);
        }
    }
    public int waysToStep(int n){
        num=n;
        ways(0);
        return count;
    }

    public int waysToStep2(int n){
        int[] array={1,2,4};
        if(n<4){
            return array[n-1];
        }
        for(int i=4;i<n+1;i++){
            int x=(array[0]+(array[1]+array[2])%1000000007)%1000000007;
            array[0]=array[1];
            array[1]=array[2];
            array[2]=x;
        }
        return array[2]%1000000007;
    }
    public static void main(String[] args) {
        Text3 t3=new Text3();
        t3.waysToStep(5);
    }
}
